package cn.algorithms_4ed.algo.sort;

/**
 * 插入排序
 * <p/>
 * 统计显示，如果数组长度为N，
 * 平均比较次数为 N*N/4，
 * 平均交换次数约为 N*N/4。
 * <p/>
 * User: erhu
 * Date: 13-6-15
 * Time: 上午11:17
 */
public class Insertion extends Sort {

    public static void main(String[] args) {
        Insertion insertion = new Insertion();
        insertion.sort().show();
        insertion.resetData().sortFaster().show();
    }

    @Override
    Sort sort() {
        return sortFaster();
        /*
        for (int i = 1; i < data.length; i++) {
            for (int j = i; j >= 1 && less(data[j], data[j - 1]); j--) {
                exchange(j, j - 1);
            }
        }

        return this;*/
    }

    @Override
    Sort sortFaster() {
        for (int i = 1; i < data.length; i++) {
            final Comparable tmp = data[i];

            int j = i;
            for (; j >= 1 && less(tmp, data[j - 1]); j--) {
                // 此处使用移位，比sort()中使用交换效率高；
                data[j] = data[j - 1];
            }
            data[j] = tmp;
        }
        return this;
    }
}
